package DataStructure.math;


//排列组合计数
public class Count {
    //二项式定理:pow(a+b,n)=sum(C(n,i)*pow(a,i)*pow(b,n-i)),其中i取[0,n]
    //卢卡斯定理:若p为质数,则对于任意整数1<=m<=n,C(n,m)=C(n%p,m%p)*C(n/p,m/p) (%p)
    //求sum(xi)=n的正整数解的组数:C(n-1,k-1); 求sum(xi)=n的自然数解的组数:C(n+k-1,k-1)

    //阶乘
    public static long fac(long n,int mod){
        if(n==0)
            return 1;
        return n%mod*fac(n-1,mod)%mod;
    }
    //预处理[0,n]的阶乘及其逆元
    public static long[][] preFac(int n,int mod){
        long[][] ans=new long[n+1][2];
        ans[0][0] = ans[0][1] = 1;
        for (int i = 1; i <= n; i ++ ) {
            ans[i][0] = ans[i-1][0] * i % mod;
            ans[i][1] = ans[i-1][1] * Maths.inv(i,mod) % mod;
        }
        return ans;
    }
    //组合数
    public static long C(long n,long m,int mod) {
        if (n >= m && m >= 0){
            if(n==m) return 1;
            m=Math.min(m, n - m);
            long ans=1;//分子分母
            for (int i = 1; i <= m; i++) {
                ans*=(n-m+i);
                ans=ans/i%mod;
            }
            return ans;
        } else return 0;
    }
    //lucas定理求组合数
    public static long lucas(long n,long m,int mod) {
        if (n < mod && m < mod) return C(n,m,mod);
        return C(n % mod, m % mod, mod) * lucas(n / mod, m / mod, mod) % mod;
    }
    //预处理C(0,0)到C(n,n)的组合数
    public static long[][] preC(int n,int mod){
        long[][] ans=new long[n+1][n+1];
        for (int i = 0; i <= n; i++) {
            ans[i][0]=1;
            for (int j = 1; j <= i; j++) {
                ans[i][j]=(ans[i-1][j]+ans[i-1][j-1])%mod;
            }
        }
        return ans;
    }
    //排列数
    public static long A(long n,long m,int mod){
        if(n>=m&&m>=0){
            long ans=1;
            for (int i = 0; i < m; i++,n--) {
                ans*=n;
                ans%=mod;
            }
            return ans;
        } else return 0;
    }
    //斐波那契数列
    public static long fib(long n,int mod){
        if(n<0)
            return -1;
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        long a=0, b=1, c=0;
        for (int i = 0; i < n - 1; i++) {
            c = (a + b)%mod;
            a = b%mod;
            b = c;
        }
        return c;
    }
    //卡特兰数

}
